import java.util.Collection;
import java.util.LinkedList;


public class nonterminal extends Rule{
	private LinkedList<ProductionRule> productionRules;
	private LinkedList<terminal> follow;
	private GlobalInteger primeCount;
	public nonterminal(String sym){
		this(sym,0);
	}

	public nonterminal(String sym, int pc){
		this(sym, null);
		this.primeCount = new GlobalInteger(pc);
	}

	private nonterminal(String sym, GlobalInteger primeCount){
		this.symbol = sym;
		this.primeCount = primeCount;
		this.productionRules = new LinkedList<ProductionRule>();
		this.follow = new LinkedList<terminal>();
	}

	public void addProductionRule(LinkedList<Rule> productionRuleList){
		this.productionRules.add(new ProductionRule(productionRuleList));
	}
	
	@SuppressWarnings("unused")
	private void addProductionRule(ProductionRule productionRule){
		this.productionRules.add(productionRule);
	}

	private void setProductionRules(LinkedList<ProductionRule> newRules) {
		this.productionRules = newRules;
	}

	public LinkedList<ProductionRule> getProductionRules() {
		return productionRules;
	}

	@Override
	public String toString(){
		return this.symbol;
	}

	public String detailedToString(){
		String ret = this.symbol+":  ";
		for(ProductionRule productionRule : this.productionRules){
			ret += productionRule.toString() + " | ";
		}
		return ret.substring(0, ret.length() - 3);
	}

 	public void printFirst(){
 		for(ProductionRule productionRule : this.productionRules){
 	 		System.out.print("First set for "+this.getSymbol()+" -> "+productionRule.toString()+":  ");
	 		for(terminal first : productionRule.getFirstList()){
	 	 		System.out.print(first.getSymbol()+", ");
	 		}
	 		System.out.println();
 		}
 	}
 	
 	public void printFollow(){
 		System.out.print("Follow set for "+this.getSymbol()+":  ");
 		for(terminal element : this.follow){
 	 		System.out.print(element.getSymbol()+", ");
 		}
 		System.out.println();
 	}

	@Override
	public boolean isTerminal(){
		return false;
	}

	@SuppressWarnings("unused")
	private GlobalInteger getPrimeCount() {
		return primeCount;
	}

	private void setPrimeCount(GlobalInteger primeCount) {
		this.primeCount = primeCount;
	}

 	private class GlobalInteger{
		private int integer;

		public GlobalInteger(int integer){
			this.integer = integer;
		}

		public void increment(){
			this.integer++;
		}

		public int getInteger(){
			return integer;
		}		
	}
 
 	@SuppressWarnings("unused")
	private class ProductionRule {
 		private LinkedList<Rule> rule;
 		private LinkedList<terminal> first;
 		
 		public ProductionRule(){
 			this.rule = new LinkedList<Rule>();
 			this.first = new LinkedList<terminal>();
 		}

		ProductionRule(LinkedList<Rule> rule){
 			this.rule = rule;
 			this.first = new LinkedList<terminal>();
 		}
 		
		public void add(Rule rule){
 			this.rule.add(rule);
 		}
 		
 		public void addFirst(Rule rule){
 			this.rule.addFirst(rule);
 		}
 		
 		public void addLast(Rule rule){
 			this.rule.addLast(rule);
 		}
 		
 		public void addAll(Collection<Rule> rules){
 			this.rule.addAll(rules);
 		}
 		
 		public Rule removeFirst(){
 			return this.rule.removeFirst();
 		}
 		
 		public Rule remove(){
 			return this.rule.remove();
 		}
 		
 		public Rule removeLast(){
 			return this.rule.removeLast();
 		}
 		
 		public void removeFirstN(int n){
 			if(n == this.rule.size())  // clearing the rule list
 			{
 				this.rule = epsilon.getEpsilonList();
 			}
 			else // remove first n
 			{		
	 			for(int i = 0; i < n; i++){
	 				this.rule.removeFirst();
	 			}
 			}
 		}
 		
 		public Rule get(int i){
 			return this.rule.get(i);
 		}
 		
 		public Rule getFirst(){
 			return this.rule.getFirst();
 		}
 		
 		public Rule getLast(){
 			return this.rule.getLast();
 		}
 		
 		public LinkedList<Rule> subList(int s, int e){
 			LinkedList<Rule> subList = new LinkedList<Rule>();
 			for(int i = s; i < e; i++){
 				subList.add(this.rule.get(i));
 			}
 			return subList;
 		}
 		
 		public boolean contains(Rule rule){
 			return this.rule.contains(rule);
 		}
 		
 		public int size() {
			return this.rule.size();
		}
 		
 		public boolean isEmpty() {
			return this.rule.isEmpty();
		}
 		
 		public String toString(){
 			String ret = "";
 			for(Rule currentRule : this.rule){
 				ret += currentRule.getSymbol()+" ";
 			}
 			return ret.substring(0, ret.length()-1);
 		}

 		private boolean firstListUnion(boolean update, LinkedList<terminal> newFirsts){
 			for(terminal newFirst : newFirsts){
 				if ( (newFirst != epsilon.getEpsilonRule()) && !this.first.contains(newFirst)){
 					this.first.addLast(newFirst);
 					update = true;
 				}
 			}
 			return update;
 		}
 		
 		public void firstListAdd(terminal rule){
 			this.first.add(rule);
 		}
 		
 		public boolean firstListContains(Rule rule){
 			return this.first.contains(rule);
 		}

		public LinkedList<Rule> getRule() {
			return rule;
		}

		public void setRule(LinkedList<Rule> rule) {
			this.rule = rule;
		}

		public LinkedList<terminal> getFirstList() {
			return first;
		}

		public void setFirstList(LinkedList<terminal> first) {
			this.first = first;
		} 		
 	}

	public nonterminal removeSelfLeftRecursion(){
		LinkedList<ProductionRule> nonLeftRules = new LinkedList<ProductionRule>();
		LinkedList<ProductionRule> leftRules    = new LinkedList<ProductionRule>();

		// Collect the left recursion entries and non-left recursion entries
		for(ProductionRule productionRule : this.productionRules){
			if(productionRule.get(0) == this) // self left recursion present
				leftRules.add(productionRule);
			else
				nonLeftRules.add(productionRule);
		}

		if(leftRules.isEmpty()) // no self-recursion present
			return null;

		// create rule-prime entry
		nonterminal rulePrime = 
			new nonterminal( this.primeString(this.symbol, this.primeCount.getInteger()+1) );		

		// add rule-prime entry to the end of the non left recursive rules
		//  i.e. A -> BC   becomes  A -> BCA'
		for(ProductionRule nonLeftRule : nonLeftRules){
			if(!nonLeftRule.getFirst().equals(epsilon.getEpsilonRule()))
				nonLeftRule.addLast(rulePrime);
		}

		ProductionRule epsilonProduction = new ProductionRule(epsilon.getEpsilonList());

		// modify rules of the form A -> AB  to  A' -> BA'
		for(ProductionRule leftRule : leftRules){
			leftRule.removeFirst();
			leftRule.addLast(rulePrime);
		}
		// add epsilon as a production rule of (what will be) rule-prime's production rules
		leftRules.add(epsilonProduction);
		// set rule-prime's production rules
		rulePrime.setProductionRules(leftRules);
		// set this grammar rule's new production rules
		this.setProductionRules(nonLeftRules);

		// increment the rules' prime count
		this.primeCount.increment();
		// set the new rule's prime count to be correct
		rulePrime.setPrimeCount(this.primeCount);

		// return the prime rule
		return rulePrime;
	}

	public LinkedList<nonterminal> removeCommonPrefixes(){

		ProductionRule prod1, prod2, newProductionRule;
		nonterminal newRule;
		LinkedList<ProductionRule> newProductionRules;
		LinkedList<nonterminal> newRules = new LinkedList<nonterminal>();
		LinkedList<ProductionRule> sharedPrefixList;

		// Loop through each combination of prod1 and prod2 and correct them if they have the same prefix
		for(int i = 0 ; i < this.productionRules.size() ; i++){
			int longestSub = 0;
			int oldLongestSub = 1;

			// create new production rule list for this grammar rule
			newProductionRules = new LinkedList<ProductionRule>();

			sharedPrefixList = new LinkedList<ProductionRule>();

			prod1 = this.productionRules.get(i);

			// Find the longest common subsequence with prod1 and the other production rules (prod2)
			for(int j = 0 ; j < i ; j++){
				prod2 = this.productionRules.get(j);
				longestSub = this.longestSubsequence(prod1, prod2);
				if(longestSub > oldLongestSub){
					newProductionRules.addAll(sharedPrefixList);
					sharedPrefixList.clear();
					sharedPrefixList.add(prod2);
					oldLongestSub = longestSub;
				}
				else if(longestSub == oldLongestSub){
					sharedPrefixList.add(prod2);
				}
				else{
					newProductionRules.add(prod2);
				}
			}
			sharedPrefixList.add(prod1);

			// Modifying this grammar rule and creating another to adjust for common prefix
			if(longestSub > 0)	// there is a common prefix
			{

				// increment the prime count
				this.primeCount.increment();

				// create new rule
				newRule = new nonterminal(this.primeString(this.symbol, this.primeCount.getInteger()),this.primeCount);

				newProductionRule = new ProductionRule();

				//Fix current grammar rule's production rules
				newProductionRule = new ProductionRule();
				newProductionRule.addAll(sharedPrefixList.get(0).subList(0, longestSub));
				newProductionRule.add(newRule);
				newProductionRules.add(newProductionRule);
				this.setProductionRules(newProductionRules);

				// Remove the common prefix
				for(ProductionRule pr : sharedPrefixList)
				{
					pr.removeFirstN(longestSub);
				}
				// Add the production rules to the new grammar rule
				newRule.setProductionRules(sharedPrefixList);
				newRules.add(newRule);
			}
		}

		if(newRules.isEmpty()) // no changes have been made
			return null;
		else // need to update grammar rules
			return newRules;		
	}

	private int longestSubsequence(ProductionRule pr1, ProductionRule pr2)
	{
		int i;
		int minLength = (pr1.size()<pr2.size()) ? pr1.size() : pr2.size();

		for(i = 0; i < minLength; i++)
		{
			if(!pr1.get(i).equals(pr2.get(i)))
				break;
		}
		return i;
	}

	/**
	 * Generate a primed version of the input string. 
	 * (i.e. if s = "A" and num = 2 then returns "A''".
	 * @param s - string to be primed
	 * @param num - number of primes to add
	 * @return
	 */
	private String primeString(String s, int num)
	{
		String removedPrimes = s.substring(0,s.length()- 1);
		int lengthMinOne = removedPrimes.length()-1;
		// remove the previous primes
		//   i.e. if s = "<ADD''> then removedPrimes will become "<ADD"
		while(removedPrimes.endsWith("'"))
		{
			removedPrimes = removedPrimes.substring(0,lengthMinOne);
			lengthMinOne--;
		}
		return removedPrimes + this.nPrimes(num) + ">";
	}

	/**
	 * Returns a string of n primes.
	 * @param n - number of ' characters
	 * @return - string of prime characters  i.e. '''''
	 */
	private String nPrimes(int n)
	{
		String ret = "";
		for(int i = 1 ; i <= n ; i++)
		{
			ret = ret+"'";
		}
		return ret;
	}

	public boolean constructFirst(boolean wasChanged)
	{
		boolean containsEpsilon;

		for(ProductionRule productionRule : this.productionRules)
		{
			containsEpsilon = true;
			for(Rule Rule : productionRule.getRule())
			{
				// union the current production rule's current grammar rule's first set with this nonterminal's first set
				wasChanged = productionRule.firstListUnion(wasChanged, Rule.getFirst());
				// if the current grammar rule doesn't contain EPSION
				if(!Rule.getFirst().contains(epsilon.getEpsilonRule())) 
				{
					// then it is safe to not examine future grammar rules
					containsEpsilon = false;
					break;
				}
			}
			if(containsEpsilon && (!productionRule.getFirstList().contains(epsilon.getEpsilonRule()))) // all grammar rules in the current production rules contained EPSILON in their first set
			{
				productionRule.firstListAdd(epsilon.getEpsilonRule());
				//wasChanged = true;
			}
		}
		return wasChanged;
	}

	public boolean constructFollow(boolean wasChanged)
	{
		int i, j, n;
		Rule RuleI, RuleIPlus;
		boolean containsEpsilon;

		RuleIPlus = null;		

		for(ProductionRule productionRule : this.productionRules)
		{
			n = productionRule.size();
			for(i = 0; i < n; i++)
			{
				RuleI = productionRule.get(i);
				if(!RuleI.isTerminal())
				{
					containsEpsilon = true;
					for(j = i+1; j < n; j++)
					{
						RuleIPlus = productionRule.get(j);
						wasChanged = this.unionFollow(wasChanged, RuleI.getFollow(), RuleIPlus.getFirst());
						containsEpsilon = containsEpsilon && RuleIPlus.getFirst().contains(epsilon.getEpsilonRule());
						if(!containsEpsilon)
						{
							break;
						}
					}
					if(containsEpsilon)
					{
						wasChanged = this.unionFollow(wasChanged, RuleI.getFollow(), this.getFollow());
					}
				}
			}
		}
		return wasChanged;
	}

	private boolean unionFollow(boolean update, LinkedList<terminal> followList, LinkedList<terminal> newFollowList){
		for(terminal newFollow : newFollowList)
		{
			if ( !followList.contains(newFollow) 
					&& (newFollow!=epsilon.getEpsilonRule()) )
			{
				followList.addLast(newFollow);
				update = true;
			}
		}
		return update;	
	}

	@Override
	public LinkedList<terminal> getFirst()
	{
		LinkedList<terminal> first = new LinkedList<terminal>();
		for(ProductionRule productionRule : this.productionRules)
		{
			first.addAll(productionRule.getFirstList());
		}
		return first;
	}

	public LinkedList<Rule> getProductionRuleForTerminal(terminal terminal){
		for(ProductionRule productionRule : this.productionRules)
		{
			if(productionRule.firstListContains(terminal))
				return productionRule.getRule();			
		}
		return null;
	}

	@Override
	public LinkedList<terminal> getFollow(){
		return this.follow;
	}
}
